The present invention relates to the improvement of a parallel multiplier which is constituted on the basis of Booth's secondary algorithm.
Various methods for realizing the performing of high-speed parallel arithmetic operations of binary form have been proposed (e.g., refer to NIKKEI ELECTRONICS, May 29, 1978, pages 76 to 89). Use of Booth's secondary algorithm is known as one of these methods. In Booth's algorithm, the product X.multidot.Y is obtained in the following manner from the data X and Y which are expressed as the 2's complement. First, the input X and Y are modified as follows: ##EQU1## where, x.sub.m and y.sub.n are sign bits and n is an even number.
The product X.multidot.Y is then modified as shown in the following expression: ##EQU2## where,
y0=0, pi=y2i+y2i+1-2.multidot.y2i+2,i=0, 1 . . . (n-1)/2, and yn is most significant bit MSB.
pi is derived by decoding three continuous bits of the multiplier Y. Pi has a value of either one of 0, .+-.1, and .+-.2. Therefore, the value of the partial product X.multidot.pi is either one of 0, .+-.X, and .+-.2X. The partial product pi.multidot.X can be produced by a simple process of inverting and/or shifting the multiplicand X, on the basis of the value of pi. The number of partial products is n/2. Therefore, in the parallel multiplier using Booth's algorithm, it is sufficient to use n/2 partial product adding circuits to add the partial products Pi.multidot.X. Accordingly, the parallel multiplier using Booth's algorithm has an advantage in that the amount of hardware necessary is less than that required by the multiplier using other algorithms. Thus, the parallel multiplier using Booth's algorithm is suitable for the realizing of a parallel multiplier of a large scale of 8.times.8 bits or more in a one-chip integrating circuit.
A circuit for adding (.+-.X.multidot.Y+Z) or subtracting (.+-.X.multidot.Y-Z) another data Z, which is expressed as the 2's complement, to or from the result of the multiplication X.multidot.Y or -X.multidot.Y, is known. FIGS. 1 and 2 show examples of the constitution of such a circuit. In FIG. 1, multiplier 1 receives the multiplicand X and multiplier Y, and obtains the product X.Y. The output of multiplier 1 is converted into -X.multidot.Y by 2's complement circuit 2. The output X.multidot.Y of multiplier 1 is selected by switch 3 which is controlled by a signal OP. The output -X.multidot.Y of 2's complement circuit 2 is selected by switch 4 which is controlled by a signal OP. The selected output X.multidot.Y or -X.multidot.Y is supplied to adding/subtracting circuit 5. The data Z is supplied to adding/subtracting circuit 5. Adding/subtracting circuit 5 performs the adding or subtracting operation on the basis of a control signal CON. In this manner, four types of product and sum calculations (.+-.X.multidot.Y.+-.Z) are selectively performed under the control of the signals OP, OP, and CON.
On the other hand, in FIG. 2, the data Z is supplied to 2's complement circuit 2. Either one of the data Z and the output -Z of 2's complement circuit 2 is selected by switch 3, which is controlled by signal OP, and switch 4 which is controlled by signal OP. The selected output is supplied to adding/subtracting circuit 5. Adding/subtracting circuit 5 adds or subtracts the output X.multidot.Y of multiplier 1 to or from data Z or -Z, on the basis of the foregoing control signals. In this manner, the four types of product sum calculations are selectively executed.
It is not desirable to use 2's complement circuit 2 in order to allow the four types of product and sum calculations to be selectively performed as mentioned above, due to the increase in the amount of hardware required. Moreover, the arithmetic operating time of 2's complement circuit 2 is long. In particular, if the parallel multiplication-type multiplier is used in order to achieve high-speed arithmetic operation, 2's complement circuit 2 is also constituted as the parallel type, so that the operating time of complement circuit 2 is long because the propagation time of the carry signal is long. If a carry look-ahead circuit is used to reduce the propagation time of the carry signal, the amount of hardware required once more increases considerably, resulting in a "vicious circle" situation.
The foregoing problems, notably the increase in the amount of hardware and the increase in the operation time also arise when the circuit for obtaining the negative product of -X.multidot.Y from the multiplicand X and multiplier Y is constituted by a multiplier for obtaining the product X.multidot.Y on the basis of Booth's secondary algorithm and a 2's complement circuit which receives the output of the multiplier as shown in FIGS. 1 and 2.